// 图
// 图在数学上的概念 G = (V, E) V - 一组顶点 E - 一组边 连接V的顶点

// 相邻顶点  AB AC AD
// 度 A - 3 E - 1
// 路径 ACDG
// 简单路径 ADG
// 环 ACDA

// 邻接矩阵
//   A  B  C  D  E  F  G  H
// A 0  1  1  1  0  0  0  0
// B 1  0  0  0  1  1  0  0

// 邻接表
// A B C D
// B A E F
// C A D G
// ...

// 关联矩阵
//   v1 v2 v3
// A  1  1  1
// B  1  0  0
// C  0  0  1
// ...

class Graph {
    constructor(isDirected = false) { // 是否有向
        this.isDirected = isDirected;
        this.vertices = []; // 存储顶点的名字
        this.adjList = new Dictionary(); // 存储邻接表
    }

    addVertex(v) { // 添加顶点
        if (!this.vertices.includes(v)) {
            this.vertices.push(v);
            this.adjList.set(v, []);
        }
    }

    addEdge(v, w) { // 添加边
        if (!this.adjList.get(v)) {
            this.addVertex(v)
        }
        if (!this.adjList.get(w)) {
            this.addVertex(w);
        }
        this.adjList.get(v).push(w);
        if (!this.isDirected) {
            this.adjList.get(w).push(v);
        }
    }

    getVertex() {
        return this.vertices;
    }

    getAdjList() {
        return this.adjList;
    }
}

// 图的遍历 BFS (广度优先搜索) DFS (深度优先搜索)
const Colors = {
    WHITE: 0, // 未访问
    GREY: 1, // 已访问 未探索
    BLACK: 2 // 已访问 已探索
}

// 算法开头需要初始化顶点状态
const initializeColor = vertices => {
    const color = {};
    for (let i = 0; i < vertices.length; i++) {
        color[vertices[i]] = Colors.WHITE;
    }
    return color;
}

// 广度优先
// 1.创建一个队列Q
// 2.标注v为被发现的 并且将v入队列Q
// 3.如果Q非空
// 3-1. 标注u 从Q出队列
// 3-2. 标注u 为被发现的(灰色)
// 3-3. 将u所有未访问过的邻点(白色)入列队
// 3-4. 标注u为已探索 黑色

export const breadthFirstSearch = (graph, startVertex, callback) => {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    const color = initializeColor(graph);

    const queue = new Queue();
    const distance = {};
    const predecessors = {};

    queue.enqueue(startVertex);

    for (let i =0; i< vertices.length; i++) {
        distance[vertices[i]] = 0;
        predecessors[vertices[i]] = null;
    }

    while (!queue.isEmpty()) {
        const u = quene.dequeue();
        const neighbors = adjList.get(u);
        color[u] = Colors.GREY;
        for (let i = 0; i < neighbors.length; i++) {
            const w = neighbors[i];
            if (color[w] === Colors.WHITE) {
                color[w] = Colors.GREY;
                distance[w] = distance[u] + 1;
                predecessors[w] = u;
                quene.enqueue(w);
            }
        }
        color[u] = Colors.BLACK;
        if (callback) {
            callback(u)
        }
        return {
            distance,
            predecessors
        }
    }
}

// 深度优先探索
// 1. 标注v - 被发现 (灰)
// 2. 标注v所有未访问(白)的邻点w，访问w
// 3. 标注v为已探索 (黑)

const depthFirstSearch = (graph, callback) => {
    const vertices = graph.getVertices();
    const adjList = graph.getAdjList();
    const color = initializeColor(graph);

    for (let i = 0; i < vertices.length; i++) {
        if (color[vertices[i]] === Colors.WHITE) {
            depthFirstSearchVisit(vertices[i], color, adjList, callback)
        }
    }
}

const depthFirstSearchVisit = (u, color, adjList, callback) => {
    color[u] = Colors.GREY;
    if (callback) {
        callback(u)
    }

    const neighbors = adjList.get(u);
    for (let i = 0; i < neighbors.length; i++) {
        const w = neighbors[i];
        if (color[w] === Colors.WHITE) {
            depthFirstSearchVisit(w, color, adjList, callback)
        }
    }
    color[u] = Colors.BLACK;
}

// 最短路径 - Dijkstra算法(贪心算法)
const INF = Number.MAX_SAFE_INTEGER;
const dijkstra = (graph, src) => {
    const dist = [];
    const visited = [];
    const { length } = graph;
    for (let i = 0; i < length; i ++) {
        dist[i] = INF;
        visited[i] = false;
    }
    dist[src] = 0;
    for (let i = 0; i < length - 1; i ++) {
        const u = minDistance(dist, visited)
        visited[u] = true;
        for (let v = 0; v < length; v++) {
            if (!visited[v] && graph[u][v] !== 0 && dist[u] !== INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v]
            }
        }
    }
    return dist;
}

const minDistance = (dist, visited) => {
    let min = INF;
    let minIndex = -1;
    for (let v = 0; v < dist.length; v++) {
        if (visited[v] === false && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// Floyd-Warshall算法
const floydWarshall = graph => {
    const dist = [];
    const { length } = graph;
    for (let i = 0; i < length; i++) {
        dist[i] = [];
        for (let j = 0; j < length; j++) {
            if (i === j) {
                dist[i][j] = 0;
            } else if (isFinite(graph[i][j])) {
                dist[i][j] = Infinity;
            } else {
                dist[i][j] = graph[i][j]
            }
        }
    }
    for (let k = 0; k < length; k++) {
        for (let i = 0; i < length; i++) {
            for (let j = 0; j < length; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
    return dist;
}